12.2 KB · ⇊ 4 parts · ⤓ Micron 12.2 KB · ⤓ HTML 36.6 KB

top

In mwdateoria della complessità, i problemi mwdqNP-difficili o mwdgNP-ardui (mwdwin inglese mweaNP-hard, da mweqnondetermistic polynomial-time hard problem, "problema difficile non deterministico in tempo polinomiale") sono una classe di problemi che può essere definita informalmente come la classe dei problemi mwegalmeno difficili come i più difficili problemi delle mwewclassi di complessità P e NP. Più formalmente, un problema mwfa H {\displaystyle H} è NP-difficile mwfqse e solo se ogni problema mwfgNP mwfw L {\displaystyle L} è mwgapolinomialmente riducibile ad mwgq H {\displaystyle H} , ovvero tale che mwgg L ≤ ≤ T H ∀ ∀ L ∈ ∈ NP {\displaystyle L\leq _{T}H\;\;\forall L\in {\text{NP}}} . In altre parole, mwgw L {\displaystyle L} deve poter essere risolto in tempo polinomiale da una mwhamacchina di Turing dotata di un oracolo per mwhg H {\displaystyle H} .cite-ref-1[1] Da questa definizione si ricava che i problemi NP-difficili sono non meno difficili dei problemi mwiwNP-completi, che a loro volta sono per definizione i più difficili delle classi P/NP.

La categoria dei problemi NP-difficili, a differenza delle classi P, NP e degli NP-completi, non è limitata per definizione ai soli problemi di decisione; vi appartengono infatti anche problemi di mwjgottimizzazione e di altri generi.

La classe dei problemi NP-difficili ha una grande rilevanza sia teorica che pratica. In pratica, dimostrare che un problema di calcolo è equivalente a un problema notoriamente NP-difficile significa dimostrare che è praticamente impossibilecite-ref-2[2] trovare un modo efficiente di risolverlo, cosa che ha molte implicazioni in mwlainformatica. Da un punto di vista teorico, lo studio dei problemi NP-difficili è un elemento essenziale della ricerca su alcuni dei principali problemi aperti della complessità.

• Osservazioni

• Esempi

• Definizione alternativa

• Convenzioni sulla nomenclatura della famiglia NP

• Note

• Bibliografia

• Collegamenti esterni

• Dato che i problemi NP-completi sono riducibili l'uno all'altro in tempo polinomiale, e tutti i problemi in NP sono riducibili in tempo polinomiale a problemi NP-completi, si ricava che dato un qualunque problema NP-difficile mwmq H {\displaystyle H} , tutti i problemi in NP sono riducibili in tempo polinomiale a esso. Di conseguenza, se si trovasse una soluzione in tempo polinomiale a un qualunque problema NP-difficile, questa potrebbe essere utilizzata per risolvere tutti i problemi in NP. Questo dimostrerebbe che mwmg P = N P {\displaystyle P=NP} . Sebbene non sia ancora stata trovata una dimostrazione, la comunità scientifica ritiene in generale che P ed NP non coincidano.cite-ref-3[3]

• Più precisamente: se mwoa P ≠ ≠ N P {\displaystyle P\neq NP} , allora i problemi NP-difficili non hanno soluzione polinomiale. Viceversa, se fosse vero che mwoq P = N P {\displaystyle P=NP} , da questo mwognon si dedurrebbe la risolubilità polinomiale dei problemi NP-difficili.

• Se un problema di ottimizzazione H ha una versione L, dove L è mwpaNP-completo, allora H è NP-difficile;

• Se H appartiene ad mwpgNP, allora H è anche mwpwNP-completo perché in tal caso la riduzione polinomiale rispetta i criteri di una riduzione tra problemi NP-completi.

Un esempio di problema NP-difficile è il problema di decisione noto come mwrgproblema delle somme parziali o "SUBSET-SUM", e che corrisponde alla domanda: dato un insieme di interi, c'è almeno un suo sottoinsieme che ha come mwrwsomma algebrica zero? Un celebre problema di ottimizzazione NP-difficile, che ha anche una fortissima valenza pratica, è quello di trovare il mwsacammino hamiltoniano che unisce due punti su un mwsqgrafo.

Ci sono mwswproblemi decisionali che sono NP-difficili ma non NP-completi, in questa classe rientrano i problemi che sono in mwtaEXPTIME, cioè tutti quei problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(mwtq 2 f ( n ) {\displaystyle 2^{f(n)}} ), dove f(n) è una funzione polinomiale. Un problema è NP-hard se tutti i problemi in NP sono riducibili polinomialmente ad esso. Un esempio di problema NP-hard è il problema delle formule booleane soddisfacibili mwtgSAT). Si può dimostrare che i problemi NP-completi sono polinomialmente riducibili a questo problema (una dimostrazione è nota per esempio per mwtw3sat). Ci sono tuttavia anche esempi di problemi che sono NP-difficili, decidibili, ma non NP-completi; un esempio è il problema del riconoscimento del linguaggio mwuaTQBF (mwuqTrue Quantified Boolean Formulas).

Una definizione alternativa di mwvaNP-hard che è spesso usata restringe NP-Hard a problemi decisionali e quindi usa la riduzione polinomiale al posto della riduzione di Turing. Così, formalmente un linguaggio mwvqL è mwvgNP-hard se mwvw ∀ ∀ L ′ ′ ∈ ∈ N P , L ′ ′ ≤ ≤ p L {\displaystyle \forall L^{\prime }\in \mathbf {NP} ,L^{\prime }\leq _{p}L} .

La nomenclatura dei problemi NP è confusa: i problemi NP-ardui non sono in NP, nonostante vengano etichettati con tale nome. Nonostante questa contraddizione verbale, tale nome è ormai di uso comune. D'altro canto, il sistema di nomenclatura mwwgNP- ha un senso più profondo, che fa interesse alla sua mwwwclasse di complessità generica, denominata anch'essa mwxaNP.

• mwxwNP-completo - identifica problemi che sono mwyacompleti mwyqdentro NP.

• mwywNP-difficile - identifica problemi che sono almeno complessi quanto quelli in NP (ma non appartengono necessariamente ad NP);

• mwzqNP-semplici - identifica problemi che sono al massimo complessi quanto quelli in NP (ma non appartengono necessariamente ad NP);

• mwzwNP-equivalenti - identifica problemi che sono esattamente equivalenti ad NP, (ma non appartengono necessariamente ad NP);

cite-note-11. ↑ Ovvero dotata di un meccanismo ipotetico che le consente di avere istantaneamente la soluzione del problema mwbgmwbwmwca mwcq mwcg mwcw mwdaH mwdq{\displaystyle H} . Se avendo la soluzione di mwdwmweamweq mweg mwew mwfa mwfqH mwfg{\displaystyle H} "gratis" la soluzione di mwgamwgqmwgg mwgw mwha mwhq mwhgL mwhw{\displaystyle L} risulta "poco costosa" (vedi la definizione di mwiqtempo polinomiale), se ne ricava che mwigmwiwmwja mwjq mwjg mwjw mwkaH mwkq{\displaystyle H} non può essere significativamente più semplice di mwkwmwlamwlq mwlg mwlw mwma mwmqL mwmg{\displaystyle L} .

cite-note-22. ↑ Uno dei problemi aperti della teoria della complessità è se sia possibile trovare un algoritmo efficiente (formalmente: in tempo polinomiale) per i problemi NP-completi. Di conseguenza, non è mwnwteoricamente impossibile che un algoritmo efficiente possa essere trovato per risolvere un problema NP-difficile. Tuttavia, nessun algoritmo del genere è mai stato identificato dalla comunità scientifica, e in generale (pur in assenza di una dimostrazione matematica) si propende per ritenere che un risultato del genere sia impossibile.

cite-note-33. ↑ La domanda "P=NP?" appartiene ai cosiddetti mwowproblemi del millennio. Sebbene la tendenza generale della comunità scientifica è a ritenere che la risposta sia "no", l'ipotesi contraria è stata formulata anche da matematici illustri come mwpaKurt Gödel.

• mwqaMichael R. Garey e David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5.

• citerefbritannica-com(EN) NP-hard problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

• citerefmathworld(EN) Eric W. Weisstein, NP-Hard Problem, su MathWorld, Wolfram Research.

• citereffoldoc(EN) Denis Howe, NP-hard, in Free On-line Dictionary of Computing. Disponibile con licenza mwrgGFDL